\section{Outline}

This outline shows how to solve the IPU game with alternative machines.

Here, I paste some Lemmas and Theorems at the beginning.

\begin{lem}\label{lem1}

The value at the extreme points of the sub-intervals $I_i$ can be calculated with processing times $t_i$ by comparing the costs of the grand coalitions where all the players use two adjacent numbers of machines.

\end{lem}

\begin{thm}\label{thm1}

$\omega(P)$ is piecewise linear, and convex in price P at each sub-interval $[P_L(m,V),P_H(m,V)]$ in $[0,P^*] $.

\end{thm}

\begin{thm}\label{thm2}

According to the foregoing description, we have the equation $P_L(V,1)=P_L(V,2)+\cdots+P_L(V,n)=\sum_{i=2}^n P_L(V,i)$.

\end{thm}

\begin{thm}\label{thm3}

The subsidy is always zero when the number of using machines, m, is larger than $\frac{n}{2}$.

\end{thm}


\begin{thm}\label{thm4}
The sum of absolute values of slopes at both sides of $P_L(V,i)$ is 1.
When the number of machines used is 1, the range of slopes of the line segments in the interval is $\left( -1 , -\frac{1}{n-1} \right]$, and the number of breakpoints is $ O(v^2) $.
\end{thm}


\begin{thm}\label{thm5}

The original problem is equivalent to using only one machine for all coalitions.

\end{thm}


\begin{thm}\label{thm6}

The IPU game with alternative machines can be solved in polynomial time.

\end{thm}


As we all know, the cost arised from the partial players in the grand coalition can be calculated handily by the SPT rule.(The corresponding conclusion see Lemma \ref{lem1}) Meanwhile, inspired by the paper (Please refer to Liu et.al.2018), we have the following approach to solve this game.


There is an effective domain $[0, P^*]$, where the grand coalition may need a subsidy from the external to maintain the balance.
(The corresponding conclusion see Theorem \ref{thm1} and \ref{thm2} where $P^* = P_L(V,1)$).


For the effective domain, we just need to divide this interval into several parts and the points are denoted as $P_L(V,i), i = 1,2,\ldots,n$.  At first, we don't need to calculate the initial part because this part the corresponding subsidy is 0 always.(The corresponding conclusion see Theorem \ref{thm3}) Then we just need to focus on the latter part which shows some interesting properties we presents above.


As we've already known that $P_L(V,i), i = 1,2,\ldots,n$ can be obtained by Lemma \ref{lem1} and Theorem \ref{thm2}, we just need to follow the CP approach(Algorithm 3) to calculate the weak derivative at each sub-interval $[P_L(m,V),P_H(m,V)]$ where the corresponding derivative is $m_V-\sum_{s\in S\subset\{V\}} \rho_s$. Then use Algorithm 1(IPC Algorithm) which will return all the breakpoints and the subsidies$\omega(P)$ during the $[0, P^*]$ to obtain the subsidy \omega(P). Notice that we can calculate the characteristic function $c(s)$ easily according to Theorem \ref{thm5}, we can formulate Theorem \ref{thm6}. Until here, we've solved the IPU game with alternative machines.
